function exchange(arr, i, j) {
  let temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

function sort(arr) {
  if (!arr || arr.length < 2) return;
  // bubbleSort(arr)
  selectSort(arr)
  // insertSort(arr)

  // mergeSort(arr, 0, arr.length - 1)
  // quickSort(arr, 0, arr.length - 1)
}

// 先序遍历
function quickSort(arr, left, right) {
  if (left < right) {
    const p = partition(arr, left, right)
    quickSort(arr, left, p[0])
    quickSort(arr, p[1], right)
  }
}

// 以arr[right]为分界点把数组分为三个区域
function partition(arr, left, right) {
  exchange(arr, left + Math.floor(Math.random() * (right - left + 1)), right)
  let less = left - 1
  let more = right + 1
  let cur = left
  while (cur < more) {
    if (arr[cur] < arr[right]) {
      exchange(arr, ++less, cur++)
    } else if (arr[cur] > arr[right]) {
      exchange(arr, --more, cur)
    } else {
      cur++
    }
  }
  return [less, more]
}

function mergeSort(arr, left, right) {
  if (left < right) {
    let mid = left + Math.floor((right - left) / 2)
    mergeSort(arr, left, mid)
    mergeSort(arr, mid + 1, right)
    merge(arr, left, mid, right)
  }
}

// left到mid有序，mid+1到right有序
function merge(arr, left, mid, right) {
  const helper = []
  let cur = 0
  let i = left
  let j = mid + 1
  while (i <= mid && j <= right) {
    helper[cur++] = arr[i] <= arr[j] ? arr[i++] : arr[j++]
  }
  while (i <= mid) {
    helper[cur++] = arr[i++]
  }
  while (j <= right) {
    helper[cur++] = arr[j++]
  }
  const len = helper.length
  for (cur = 0; cur < len; cur++) {
    arr[left + cur] = helper[cur]
  }
}

// 插入排序，扑克牌
function insertSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i - 1; j >= 0; j--) {
      if (arr[j + 1] < arr[j]) {
        exchange(arr, j, j + 1)
      } else {
        // 跳出当前循环，因为前面已经有序，不需要比较了
        break;
      }
    }
  }
}

// 选择排序
function selectSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }
    exchange(arr, i, minIndex)
  }
}

function bubbleSort(arr) {
  for (let end = arr.length - 1; end > 0; end--) {
    for (let i = 0; i < end; i++) {
      if (arr[i] > arr[i + 1]) {
        exchange(arr, i, i + 1)
      }
    }
  }
}

const arr = [2, 5, 6, 7, 3, 2, 3, 5, 7, 1, 1, 2, 33, 11, 2, 3, 4]
sort(arr)
console.log(arr)